package com.qying.sort;

import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = Number.arr;

        for (int i : arr) {
            System.out.print(i + ",");
        }
        System.out.println();

        arr = quickSort(arr, 0, arr.length-1);

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    private static int[] quickSort(int[] arr, int start, int end) {
        if (arr.length < 1|| start < 0||end > arr.length || start > end)
        {
            return null;
        }

        int smallIndex = partition(arr, start, end);

        if (smallIndex > start)
            quickSort(arr,start, smallIndex-1);
        if (smallIndex < end)
            quickSort(arr, smallIndex+1,end);
        return arr;
    }

    private static int partition(int[] arr, int start, int end) {
        int poivt = (int) (start + Math.random()* (end-start + 1));

        int samllIndex = start -1;

        swap(arr, poivt, end);

        for (int i = start; i<= end;i++){
            if (arr[i] <= arr[end]){
                samllIndex ++;
                if (i > samllIndex)
                    swap(arr,i,samllIndex);
            }
        }
        return samllIndex;
    }



    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
